1. Technical Field
The field of this invention is data processing, or more specifically, methods, systems, and products for managing virtual memory in a multi-processor computer.
2. Description of the Related Art
In a computer system Random Access Memory (RAM) contains the instructions (program) to execute and the data necessary to execute those instructions. The resulting data from execution of the program code is also stored back into the RAM.
Modem computer systems use Virtual Memory Management (VMM) with on demand paging to extend the size of memory. Modem computer systems can do this as only the actual instructions and data required at a given point in time for execution need to reside in memory.
For efficiency, real memory is divided into units, often of equal sizes. These units are referred to herein as pages or frames. When a portion of a program's code or data is needed in RAM, it will be bought in one page at a time. Equally, when a portion of a program or data is no longer needed in RAM it will be removed from the RAM a page at a time to make room for other instructions or data.
The VMM manages the translation between the effective size of memory (effective memory address range) and the physical size of memory (physical memory address range). The VMM maintains a map, which is used to translate the effective address of a page to the physical location of that page in RAM. This is known as a page translation, and the entries in this map are called Page Translation Entries (PTE). When an effective memory address is accessed which is
not in physical memory a page fault occurs. To satisfy the page fault and allow execution to continue, a page in memory will be selected for replacement if there are no free pages in memory.
The VMM is responsible for selecting the page to replace, removing the contents of that page out of RAM, removing the PTE, loading the new page into memory, and adding a PTE. Once this has been done execution of the faulting program is free to continue.
The VMM can use a variety of page replacement policy considerations when selecting pages in memory to be replaced with newly requested data including how recently the page was last accessed, and the number of times it has been bought back into memory (repaged). The most common method employed in modern computer systems is some variant of a Least Recently Used (LRU) algorithm. Other considerations or policies are often tied into the LRU policy to weight the decision to remove a page either more or less favored against other potential candidates. In some cases many pages will need to be examined in RAM before a suitable candidate can be found.
Finding a suitable candidate page in memory to replace can be a lengthy process. In addition, removal of a page from memory can be a lengthy process as the contents of the page being removed will need to be save to physical storage if it's contents have been changed since being loaded into the RAM.
For efficiency, the VMM always tries to keep free pages available in RAM. If free pages are available in RAM the page fault takes less time to satisfy as the VMM does not need to find a suitable candidate in memory to replace, nor does it need to save the contents of the page if changes have occurred to the page since being bought into RAM. For efficiency, pages which are available for immediate replacement (unallocated) are entered into a freelist. When the VMM needs to satisfy a page request it first checks for a free page on this list.
In order to increase the chances that there will be free page on the free list when a page fault occurs, RAM is scanned and ideal candidates selected and removed from RAM prior to being needed. This is done by maintaining a count of the number of available free pages. If the number of free pages available drops below a predetermined and often tunable value, a scan of RAM using the VMM's page replacement policy is initiated to look for suitable pages to free and add to the freelist. When the frequency of page faults exceed the ability of the VMM to keep pages available on the freelist page faults must then wait to have their page fault satisfied until the VMM is able to free a page. Once pages become available, threads waiting on pages compete for page allocations. Some may get all the pages needed, while others may get only some or none of the pages requested. In the case that the thread only gets some of the needed pages, this can lead to fragmentation of follow-on requests such as I/O operations done in multiple smaller blocks instead of one larger operation. In addition, a thread with only a portion of it's required pages may remain blocked, thereby holding pages which could have been used to make further progress by another competing thread.
Other known strategies for dealing with these problems are to regionalize memory. For example, only certain types of memory requests (for example requests for file pages) are allowed to utilize a percentage of memory. This however can cause memory request to fail and therefore wait even when there are free memory pages available. It also drives up the scan to free ratio as the number of candidate pages decreases (i.e. if only 20% of memory is allocated for file pages and a scan for file pages is commenced, statistically only one in 5 pages inspected will be of the right type).